package com.sxu.fighting.day1;

import java.util.Arrays;

/**
 * 169
 */
public class Test4 {
    // 对原数组排序， n/2 位置一定是众数
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    // 快速选择算法
    public int majorityElement2(int[] nums) {
        // 查找第 k 个元素（k = 数组长度一半位置）
        return quick(nums, 0, nums.length - 1, nums.length / 2);
    }

    private int quick(int[] nums, int l, int r, int k) {
        // 递归终止条件：只剩一个元素
        if (l == r) return nums[l];

        // 初始化 左 右指针
        int i = l - 1, j = r + 1;
        int x = nums[l];  // 基准值（可优化为随机选择）

        // 分区操作（降序排列）
        while (i < j) {
            // 从左找第一个 <= x 的元素
            do i++; while (nums[i] > x);
            // 从右找第一个 >= x 的元素
            do j--; while (nums[j] < x);
            // 交换逆序对
            if (i < j) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }

        // 递归选择分区
        if (k <= j)
            return quick(nums, l, j, k);   // 在左分区继续查找
        else
            return quick(nums, j + 1, r, k); // 在右分区继续查找
    }

    // Boyer-Moore投票算法
    public int majorityElement3(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}
